/*
问题：用栈实现队列
方法：用两个栈
插入 s1借助辅助栈s2将元素插入到栈底
删除 s1栈顶元素pop
访问 访问s1栈顶元素
判断 判断s1是否为空

使用栈实现队列的下列操作：

push(x) -- 将一个元素放入队列的尾部。
pop() -- 从队列首部移除元素。
peek() -- 返回队列首部的元素。
empty() -- 返回队列是否为空。


Two Stacks, push O(n), pop O(1)
/*
 * @lc app=leetcode.cn id=232 lang=cpp
 *
 * [232] 用栈实现队列
 */

#include <stack>

class MyQueue
{
private:
  // 主栈
  stack<int> s1;
  // 辅助栈
  stack<int> s2;

public:
  MyQueue()
  {
  }

  /* Push element x to the back of queue. */
  void push(int x)
  {
    // s1转移到s2
    while (!s1.empty())
    {
      s2.push(s1.top());
      s1.pop();
    }
    // 在s1中插入元素（处在栈底位置） 栈底作为队列rear
    s1.push(x);
    // s2z转移回s1
    while (!s2.empty())
    {
      s1.push(s2.top());
      s2.pop();
    }
  }

  /** Removes the element from in front of queue and returns that element. */
  // 出队
  int pop()
  {
    int top_element = s1.top();
    s1.pop();
    return top_element;
  }

  /** Get the front element. */
  int peek()
  {
    return s1.top();
  }

  /** Returns whether the queue is empty. */
  bool empty()
  {
    return s1.empty();
  }
}

/**
 * Your MyQueue object will be instantiated and called as such:
 * MyQueue* obj = new MyQueue();
 * obj->push(x);
 * int param_2 = obj->pop();
 * int param_3 = obj->peek();
 * bool param_4 = obj->empty();
 */

// @lc code=end